A connected region is defined by its outlines or boundaries within which it lies. The boundary set of a region is a significantly “thinner” set that captures the extent and geometry of the region concisely. This property makes boundaries or contours attractive representatives of regions in image analysis to economize the representation of regional information without compromise. It is also easier and more efficient to manipulate regional information through contours by operations such as smoothing, sub-sampling, de-noising, etc.
Object boundary extraction from binary images is important for many applications, e.g., automatic interpretation of images containing segmentation results, printed and handwritten documents and drawings, maps, and AutoCAD drawings. Efficient and reliable contour extraction is also important for pattern recognition due to its impact on shape-based object characterization and recognition. There have been many processes proposed in the references below for contour extraction from binary images. None of these processes guarantee non-intersecting contours or associate the contours with foreground regions they bound.
U.S. Pat. No. 6,173,075, issued Jan. 9, 2001, to Collins, describes a method for converting a pixel map of a drawing into a series of points that define outer and inner perimeters. The process first locates boundary pixels and then finds pixel edge points on the boundary. Rather than locate pixel boundary edge points directly, a complex series of determinations is made as the process traces back through each boundary pixel after all of the boundary pixels are located. It is desirable to locate boundary points directly and sequentially.
Further, the process taught in the '075 patent conveniently acts to associate a new region with a new outer contour that is located. But if the new contour is an inner contour, all of the outer contour regions must be examined to determine which one contains the inner contour.